#
# @lc app=leetcode.cn id=878 lang=python3
#
# [878] 第 N 个神奇数字
#

# @lc code=start
class Solution:
    def gcd(self, a: int, b: int) -> int:
        return a if b == 0 else self.gcd(b, a % b)

    def lcm(self, a: int, b: int) -> int:
        return (a * b) / self.gcd(a, b)

    def maginNumber(self, n: int, a: int, b: int) -> int:
        return n // a + n // b - n // self.lcm(a, b)

    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        mod = 10 ** 9 + 7
        l, r = min(a, b), n * min(a, b)
        while l < r:
            mid = l + (r - l) // 2
            if (self.maginNumber(mid, a, b) < n):
                l = mid + 1
            else:
                r = mid
        return l % mod

 # @lc code=end
